//请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都
//是O(1)。 
//
// 若队列为空，pop_front 和 max_value 需要返回 -1 
//
// 示例 1： 
//
// 输入: 
//["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
//[[],[1],[2],[],[],[]]
//输出: [null,null,null,2,1,2]
// 
//
// 示例 2： 
//
// 输入: 
//["MaxQueue","pop_front","max_value"]
//[[],[],[]]
//输出: [null,-1,-1]
// 
//
// 
//
// 限制： 
//
// 
// 1 <= push_back,pop_front,max_value的总操作数 <= 10000 
// 1 <= value <= 10^5 
// 
// Related Topics 设计 队列 单调队列 👍 310 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;

public class DuiLieDeZuiDaZhiLcof {
    public static void main(String[] args) {
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class MaxQueue {
        /**
         * 这一题也可以看成是滑动窗口的题目，添加元素时窗口向右扩大
         * 元素出队列时窗口缩小
         * max队列中按照递减顺序保留可能的当前窗口的最大值
         * 和上一题不一样的地方是：上一题是固定的窗口进行滑动，本题目的窗口是随机扩大和缩小的
         */
        Queue<Integer> data;// 普通队列queue正常保存所有数据
        Deque<Integer> max;// 双端队列，保存可能的最大值，非严格递减队列
        public MaxQueue() {
            data = new ArrayDeque<>();
            max = new ArrayDeque<>();
        }
        // 队列中所有元素的最大值
        public int max_value() {
            return max.isEmpty() ? -1 : max.peekFirst();
        }
        // 添加到尾部
        public void push_back(int value) {// 窗口扩大
            data.add(value);
            while (!max.isEmpty() && value > max.peekLast()) max.pollLast();// 小于当前值的全部从尾部出队列
            max.addLast(value);
        }
        // 这里是先入先出的
        public int pop_front() {// 窗口缩小
            if (data.isEmpty()) return -1;
            int res = data.poll();
            if (!max.isEmpty() && res == max.peekFirst()) max.pollFirst();// 如果当前出数据队列值为最大值，最大值左出一个
            return res;
        }
    }

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */
//leetcode submit region end(Prohibit modification and deletion)

}